package com.yx.study.leet.questionList.questionTwo;

import org.junit.Test;

import java.util.Arrays;

/**
 * 56. 合并区间
 * https://leetcode.cn/problems/merge-intervals/description/
 */
public class Solution56 {
    public int[][] merge(int[][] intervals) {
        // 排序 根据首位排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        int[][] res = new int[intervals.length][2];
        int index = -1;
        // 遍历
        for (int[] interval : intervals) {
            // 如果res数组是空的,或者当前区间的起始位置>res数组中最后区间的终止位置,则不合并,直接将当前区间加入res数组
            if (index == -1 || interval[0] > res[index][1]) {
                res[++index] = interval;
            } else {
                // 反之将当前区间合并至res数组的最后区间
                res[index][1] = Math.max(res[index][1], interval[1]);
            }
        }
        return Arrays.copyOf(res, index + 1);
    }

    @Test
    public void test() {
        int[][] intervals = new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        System.out.println(Arrays.deepToString(merge(intervals)));
    }
}
